import java.util.ArrayList;
import java.util.List;

public class Test3 {
    public TreeNode balanceBST(TreeNode root){
        List<Integer> sortList = new ArrayList<>();
        inOrder(root,sortList);
        return buildTree(sortList,0,sortList.size()-1);

    }

    private TreeNode buildTree(List<Integer> sortList, int start, int end) {
        if (start > end){
            return null;
        }
        int mid = start + (end-start)/2;
        TreeNode root = new TreeNode(sortList.get(mid));
        root.left = buildTree(sortList, start, mid-1);
        root.right = buildTree(sortList,mid+1,end);
        return root;
    }

    private void inOrder(TreeNode node, List<Integer> sortList) {
        if(node != null){
            inOrder(node.left,sortList);
            sortList.add(node.val);
            inOrder(node.right,sortList);
        }
    }
}
